'''
单调栈
经典用法：
用于获得每个位置 左边比我小的位置L，右边比我小的位置R
隐含的表示了，在 L+1 ~ R-1, 这个范围上，我就是最小的

大的同理

考虑== 的情况。是否要处理，要出栈。 以及如果相等的时候出栈了，答案是不是有漏掉或者是否需要在补充


宽泛用法：
    根据单调性入栈；[可选淘汰掉对后续计算没有帮助的栈里的元素]
    出栈后，这个元素计算答案；不在参与后续的流程了


'''
from collections import deque


# 返回数组ans ans[i] = [li, ri]
#       li: arr中比arr[i] 小的左边位置
#       ri: arr中比arr[i] 小的右边位置
def f(nums):
    n = len(nums)
    ans = [[-1, -1] for _ in range(n)]
    # 入栈，与收集答案
    stack = deque([])
    for i, num in enumerate(nums):
        if not stack or num > nums[stack[-1]]:
            # 如果栈中没有元素，或者我比栈中元素大，进栈
            stack.append(i)
        else:
            while stack and nums[stack[-1]] >= num:
                target = stack.pop()
                ans[target][0] = stack[-1] if stack else -1
                ans[target][1] = i  # 如果没有重复值没有问题。但是有重复值即arr[target] == arr[i],
                # 那么后续还需要调整这个答案，为后续正确的。
                # 例如这有一个重复值，那他右边的答案可能是i位置的右边的答案，或者是i位置还不对是更右边
                # 所以后续还需从右向左修复答案
            stack.append(i)
    # 将剩余在栈中的元素收集答案
    while stack:
        target = stack.pop()
        ans[target][0] = stack[-1] if stack else -1
        ans[target][1] = -1  # 没有右边比自己小的

    # 修复重复值之间的答案
    for i in range(n - 1, -1, -1):
        target = ans[i][1]
        if target != -1 and nums[i] == nums[target]:
            # 如果，我是重复值，且我是被重复值干出栈的，那我的答案，就依赖于右边这位
            ans[i][1] = ans[target][1]
    return ans


nums = [2, 3, 4, 3, 2, 1, 3, 5, 6, 3, 4, 3, 2]
ans = f(nums)
print(ans)
